package sort;

import org.junit.Test;

import java.util.Arrays;

public class QuickSort {

    @Test
    public void test() {
        System.out.println(Arrays.toString(quickSort()));
        System.out.println(Arrays.toString(quickSort(1)));
        System.out.println(Arrays.toString(quickSort(1, 2)));
        System.out.println(Arrays.toString(quickSort(2, 1)));
        System.out.println(Arrays.toString(quickSort(1, 2, 3)));
        System.out.println(Arrays.toString(quickSort(1, 3, 2)));
        System.out.println(Arrays.toString(quickSort(2, 1, 3)));
        System.out.println(Arrays.toString(quickSort(2, 3, 1)));
        System.out.println(Arrays.toString(quickSort(3, 1, 2)));
        System.out.println(Arrays.toString(quickSort(3, 2, 1)));
    }

    public static int[] quickSort(int... nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }

    // sort [start, end]
    public static void quickSort(int[] nums, int start, int end) {
        if (end <= start) {
            return;
        }
        int pivotIndex = partition(nums, start, end);
        quickSort(nums, start, pivotIndex-1);
        quickSort(nums, pivotIndex+1, end);
    }

    // KEYNOTE: condition 'i<j' should appear in both outer and inner while condition
    public static int partition(int[] nums, int start, int end) {
        int i = start;
        int j = end;
        int pivot = nums[start];
        while (i < j) {
            while (i < j && nums[j] >= pivot) { // both '>' or '>=' is ok
                j--;
            }
            //if (i < j) { // the condition can be omitted
                nums[i] = nums[j];
                //i++; // this decrement can be omitted
            //}
            while (i < j && nums[i] <= pivot) { // both '<' or '<=' is ok
                i++;
            }
            //if (i < j) { // the condition can be omitted
                nums[j] = nums[i];
                //j--; // this decrement can be omitted
            //}
        }
        nums[i] = pivot;
        return i;
    }
}
